package main

import "fmt"

type Node struct {
	val         int
	left, right *Node
}

func NewTree(elements []int) (root *Node) {
	if len(elements) == 0 {
		return
	}
	return createTree(elements, 0)
}

func createTree(elements []int, index int) (root *Node) {
	if index >= len(elements) {
		return
	}
	root = &Node{val: elements[index]}
	root.left = createTree(elements, 2*index+1)
	root.right = createTree(elements, 2*index+2)
	return
}

func postOrder(root *Node) {
	if root == nil {
		return
	}
	postOrder(root.left)
	postOrder(root.right)
	fmt.Printf("%d ", root.val)
}

func main() {
	values := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
	tree := NewTree(values)
	postOrder(tree)
	fmt.Println()
}
